BPP là đóng với phép lấy phần bù; nghĩa là, BPP = co-BPP. BPP là thấp cho chính nó, nghĩa là một máy BPP với khả năng giải quyết bài toán BPP ngay tức thì (một máy tiên tri BPP) không mạnh hơn phiên bản thông thường. Nghĩa là, BPPBPP = BPP.

Mối liên hệ giữa BPP và NP là không rõ: chưa biết liệu BPP có là tập hợp con của NP, NP có là tập hợp con của BPP hay chúng không thể so sánh được. Nếu NP nằm trong BPP (thường được coi là khó có thể xảy ra do nó dẫn đến thuật toán hiệu quả cho các bài toán NP-đầy đủ), thì NP = RP và PH ⊆ BPP.[3]

RP là tập hợp con của BPP, và BPP là tập hợp con của PP. Hiện vẫn chưa biết liệu hai mối quan hệ tập hợp cha-con đó có chặt hay không. Ngay cả việc P có là tập hợp con thực sự của PSPACE vẫn chưa được chứng minh. BPP nằm trong tầng thứ hai của cấp bậc đa thức và do đó nằm trong PH. Cụ thể hơn, định lý Sipser–Lautemann phát biểu rằng BPP ⊆ Σ2 ∩ Π2. Do đó, P = NP dẫn tới P = BPP do trong trường hợp này, PH bằng P. Vì vậy, hoặc P = BPP hoặc P ≠ NP hoặc cả hai.

Định lý Adleman phát biểu rằng mọi ngôn ngữ trong BPP đều có thể quyết định bởi một gia đình các mạch lôgic Bool, nghĩa là BPP nằm trong P/poly.[4] Thực vậy, mọi thuật toán BPP cho dữ liệu vào có độ dài cố định đều có thể được chuyển thành đơn định bằng cách dùng một chuỗi bit ngẫu nhiên cố định. Tuy nhiên, việc tìm ra chuỗi đó có thể rất khó.

Tồn tại hai máy tiên tri A và B, sao cho PA = BPPA và PB ≠ BPPB. Hơn nữa đối với máy tiên tri ngẫu nhiên với xác suất 1, P = BPP và BPP nằm trong NP và co-NP.[5]